package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - 下降路径最小和
        Solution solution1 = new Solution();
        System.out.println("下降路径最小和:");
        int[][] matrix1 = {{2, 1, 3}, {6, 5, 4}, {7, 8, 9}};
        System.out.println("matrix=[[2,1,3],[6,5,4],[7,8,9]]: " + solution1.minFallingPathSum(matrix1)); // 13
        int[][] matrix2 = {{-19, 57}, {-40, -5}};
        System.out.println("matrix=[[-19,57],[-40,-5]]: " + solution1.minFallingPathSum(matrix2)); // -59

        // 测试用例 - 珠宝的最高价值
        Solution2 solution2 = new Solution2();
        System.out.println("\n珠宝的最高价值:");
        int[][] frame1 = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println("frame=[[1,3,1],[1,5,1],[4,2,1]]: " + solution2.jewelleryValue(frame1)); // 12
    }

    // 下降路径最小和
    static class Solution {
        int[][] dp;

        public int minFallingPathSum(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            dp = new int[m + 1][n + 1];

            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    int cur = dp[i - 1][j];  // 正上方
                    if (j > 1) cur = Math.min(cur, dp[i - 1][j - 1]);  // 左上方
                    if (j < n) cur = Math.min(cur, dp[i - 1][j + 1]);  // 右上方
                    dp[i][j] = matrix[i - 1][j - 1] + cur;  // 注意索引映射
                }
            }

            int ret = Integer.MAX_VALUE;
            for (int j = 1; j <= n; j++) {  // 遍历最后一行的所有列
                ret = Math.min(ret, dp[m][j]);
            }

            return ret;
        }
    }

    // 珠宝的最高价值
    static class Solution2 {
        int[][] dp;

        public int jewelleryValue(int[][] frame) {
            int m = frame.length, n = frame[0].length;
            dp = new int[m + 1][n + 1];  // 1-索引，自动处理边界

            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    // 当前价值 = 当前珠宝 + max(从上来, 从左来)
                    dp[i][j] = frame[i - 1][j - 1] + Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }

            return dp[m][n];  // 右下角就是答案
        }
    }
}